\documentclass[a4paper,12pt]{article}
\usepackage{fancyhdr}
\usepackage[MeX]{polski}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[ lmargin=2.7cm]{geometry}
\usepackage{graphicx}
\usepackage{grffile}


\pagestyle{fancy}
\lhead{Zastosowanie algorytmu ewolucyjnego z heurystykami do rozwiązania problemu QAP}
\rhead{\bfseries}

\newcommand{\aindent}{\hspace{4em}}

\author{Adrian Chudziński, Przemysław Gospodarczyk}
\title{Zastosowanie algorytmu ewolucyjnego z heurystykami do rozwiązania problemu QAP -- raport}

\begin{document}
\makeatletter
    \renewcommand\@seccntformat[1]{\csname the#1\endcsname.\quad}
    \renewcommand\numberline[1]{#1.\hskip0.7em}
\makeatother

\begin{titlepage}
\begin{center}

    \textsc{Studencki Projekt nr. 2 z Algorytmów Ewolucyjnych}\\[0.1cm]
    \textsc{IIUWr 2010/2011}\\[6cm]
    Adrian Chudziński, Przemysław Gospodarczyk\\[1cm]
    \textsc{\Large Zastosowanie algorytmu ewolucyjnego z heurystykami do rozwiązania problemu QAP }\\[0.25cm]
    \textsc{\large raport}\\[8.675cm]
    \begin{tabular}{ | c | p{4cm} | p{4.25cm} | c | }
        \hline
        {\footnotesize Wersja}  &
        {\footnotesize Zmiany}  &
        {\footnotesize Autor} &
        {\footnotesize Data}    \\
        \hline
        {\footnotesize 1.0}                                                                   &
        {\footnotesize Pierwsza wersja}                                                          &
        \par {\footnotesize Adrian Chudziński \par Przemysław Gospodarczyk}                                          &
        {\footnotesize 2011-01-26}                                                            \\
        \hline
    \end{tabular}
\end{center}
\end{titlepage}
\break

\setcounter{page}{2}

\tableofcontents

\break

\section[Opis problemu, dane wejściowe, kodowanie i interpretacja rozwiązań oraz funkcja celu]{Opis problemu, dane wejściowe, kodowanie i interpretacja rozwiązań oraz funkcja celu}
\noindent Kwadratowy problem przydziału (ang. \emph{Quadratic assignment problem -- QAP}) to jeden z najważniejszych NP-trudnych problemów optymalizacji kombinatorycznej. Przedstawiona poniżej interpretacja tego problemu jest jedną z wielu znanych.
\par Dysponujemy zbiorami \texttt{N} fabryk i \texttt{N} lokacji oraz dwoma kwadratowymi macierzami rozmiaru \texttt{N} (macierz \texttt{d} odległości między każdą parą lokacji i macierz \texttt{f} wag między każdą parą fabryk), gdzie \texttt{N} jest parametrem algorytmu (liczbą naturalną).
\par Zadanie polega na przypisaniu każdej z fabryk do jednej z lokacji (każdą do innej) tak, aby zminimalizować sumę iloczynów dystansów między lokacjami i odpowiadających wag. W praktyce chodzi o minimalizację pewnej funkcji celu:

\begin{equation}
\min_{p \in \Pi}{\sum_{i = 1}^{N} \sum_{j = 1}^{N}d[i][j]*f[p[i]][p[j]]}
\end{equation}

\noindent gdzie \texttt{p} jest wektorem przypisania.\\
Wektor przypisania jest w rzeczywistości permutacją liczb naturalnych z zakresu [0,N), gdzie na i-tym polu odpowiadającym i-tej lokacji znajduje się numer fabryki, która jest przypisana do tej lokacji.
\\

Przedstawiona w definicji interpretacja jest jedną z wielu, QAP zastosować można też w:
\begin{itemize}
    \item[-] szeregowaniu zadań (ang. \emph{scheduling});
    \item[-] analizie danych statystycznych;
    \item[-] wyszukiwaniu informacji (ang. \emph{information retrieval});
    \item[-] transporcie;
    \item[-] problemach optymalizacji kombinatorycznej (szukanie maksymalnej kliki w grafie, problem komiwojażera, problemy podziału grafów).
\end{itemize}

\section[Źródło danych]{Źródło danych}
Wszystkie zestawy danych testowych w postaci plików o rozszerzeniu \texttt{.DAT} pochodzą z serwisu QAPLIB - A Quadratic Assignment Problem Library (adres \cite{QAPL}). Struktura pliku z danymi składa się z trzech części:
\begin{itemize}
    \item[-] liczba naturalna \texttt{N};
    \item[-] poprzedzona pustym wierszem zawartość macierzy \texttt{f} (w każdej z N linijek jeden wiersz macierzy, zawierający N kolumn, w każdym polu liczba naturalna);
    \item[-] poprzedzona pustym wierszem zawartość macierzy \texttt{d} (w każdej z N linijek jeden wiersz macierzy, zawierający N kolumn, w każdym polu liczba naturalna).
\end{itemize}
Serwis udostępnia ponadto najlepsze znane rozwiązania dla wszystkich udostępnionych testów, w postaci pliku z permutacją minimalizującą wartość funkcji celu. Dane są również informacje o tym, czy najlepsze znane rozwiązanie jest optymalne (wartości graniczne, które są możliwe do osiągnięcia ale nieznana są permutacje, które te wartości generują).

\section[Algorytm]{Algorytm}

\subsubsection[Rodzaje populacji, ich rozmiary i kryteria]{Rodzaje populacji, ich rozmiary i kryteria}
Generujemy startowy zbiór rozwiązań wykorzystując wiedzę o typie problemu, zdając sobie sprawę z wielowymiarowości dużej przestrzeni poszukiwań.
Pewna z góry ustalona liczba mówi nam ile chcemy rozwiązań najlepszej jakości, a ile najbardziej różnorodnych -- najbardziej odległych od rozwiązań z najlepszej populacji (one rozszerzają nam przestrzeń poszukiwań i zmniejszają prawdopodobieństwo zbieżności do ekstremum lokalnego). Domyślnie algorytm tworzy obie populacje tej samej wielkości.
Można stosować wyspecjalizowane heurystyki, ulepszające zbiory startowe (zmniejszające wartości funkcji celu dla najlepszej populacji i gwarantujące większe zróżnicowanie wśród różnorodnej populacji).\\

\subsection[Inicjowanie obu populacji (metoda Glovera)]{Inicjowanie obu populacji (metoda Glovera)}

Generujemy wektory całkowitoliczbowe, przykładowo dla \texttt{N = 12} mamy następujący wektor przypisania:\\
\texttt{x = (10, 1, 3, 5, 6, 2, 12, 8, 4, 7, 9, 11)}, co oznacza, że 1. firma ma siedzibę w lokacji 10., 2. firma w lokacji 1. itd...
Wykorzystano tzw. metodę Glovera, która gwarantuje pewien poziom zróżnicowania w zbiorze rozwiązań (w przeciwieństwie do podejścia czysto losowego), zaspokaja kryterium różnorodności. Wygenerowane przez metodę wektory są poprawnymi permutacjami i nie trzeba ich naprawiać.\\
Jako ziarno wykorzystujemy 1 losową, poprawną permutację x.
Na podstawie ziarna tworzymy nowe rozwiązania.\\
\textbf{Dane:}
\begin{itemize}
    \item[-] b – naturalne, mniejsze od N, zmienna oznacza krok w iteracji (losowa wartość z przedziału [1, N/2]);
    \item[-] s – pozycja startowa, na początku równa b.
\end{itemize}
\textbf{Algorytm:}\\ Rozwiązanie x' budujemy dodając najpierw element \texttt{x[s]}, potem kolejno \texttt{x[s + b],
x[s + 2b], …, x[s + rb]}, gdzie r jest tak dobrane, że
\texttt{s+rb} nie przekracza N. Kiedy dojdziemy do końca ziarna, to pozycja startowa zmniejsza się o 1 i cała operacja się powtarza aż nie zapełnimy całego wektora x' (musimy odwiedzić wszystkie pozycje w x).\\
W praktyce dla każdego ziarna algorytm generuje po 10 osobników.

\subsubsection[Heurystyka usprawniająca (kryterium minimalizacji funkcji celu)]{Heurystyka usprawniająca (kryterium minimalizacji funkcji celu)}
Dla najlepszej populacji wygenerowanych osobników stosujemy
metodę przeszukiwania tabu Erica Taillarda dla QAP.\\
Dla każdego osobnika niezależnie, heurystyka iteruje cały chromosom i oblicza możliwe zamiany lokacji dwóch sąsiednich firm, wykorzystując prostą listę tabu (ruchy niedozwolone).
Aby zmusić algorytm do przeszukiwania niezbadanych fragmentów przestrzeni, wymieniane są ze sobą tylko te elementy, które nie były wymieniane przez kilka ostatnich iteracji (na podstawie listy tabu, ruchy niedozwolone to takie, które wykonano wcześniej niż 5 iteracji temu).
Jeżeli jednak, zabroniona zmiana doprowadza do wyprodukowania najlepszego nieznanego do tej pory przez algorytm rozwiązania, to zamiana się dokonuje, mimo obecności ruchu na liście tabu (ang. \emph{aspiration criterion}).\\
Jeżeli zamiana jest dozwolona ale pogarsza wartość funkcji celu dla zmodyfikowanego osobnika to do zamiany nie dochodzi.

\subsubsection[Wybór rodziców i krzyżowanie]{Wybór rodziców i krzyżowanie}
Wszystkie rozwiązania z obu rodzajów populacji łączymy w pary (metoda każdy z każdym).
Stosujemy metodę path-relinking.\\
Wektorami wiodącymi, zostają te, które są lepsze w swojej parze (lepiej optymalizują f. celu), potomek jest inicjowany wektorem niewiodącym.
Iterujemy wektory.\\ Jeżeli na napotkanej pozycji wektory rodziców nie różnią się, to odpowiadająca pozycja w potomku jest pozostawiana.
\\Jeżeli na napotkanej pozycji wektory rodziców różnią się oraz pozycja ta w potomku nie była wcześniej zmieniana to do potomka przepisywana jest wartość z wektora wiodącego (pod warunkiem, że nie pogarsza wartości funkcji celu).\\ Jeżeli zamiana miałaby dotyczyć pozycji już rozważanej to kolejna zamiana nie jest rozważana (algorytm nigdy nie robi zamiany wstecz).\\ Otrzymany w ten sposób osobnik potomny jest poprawną permutacją.

\subsubsection[Zamiana pokolenia]{Zamiana pokolenia}
Liczba otrzymanych osobników potomnych w poprzednim kroku znacznie przewyższa liczbę obu populacji.
Niech R1 to zbiór najlepszych rozwiązań oraz niech R2 to zbiór najbardziej zróżnicowanych rozwiązań.\\
Nowe rozwiązanie wchodzi do R1, jeżeli jest lepsze niż najgorsze z tego zbioru i nie ma jego kopii ani w R1 ani w R2.
Nowe rozwiązanie wchodzi do R2, jeżeli jest bardziej zróżnicowane niż najmniej zróżnicowane z tego zbioru i nie ma jego kopii ani w R1 ani w R2.\\
Różnorodność rozwiązania x jest zdefiniowana jako dystans między tym rozwiązaniem, a wszystkimi rozwiązaniami \textbf{z R1 oraz z R2}.
Zapobiega to zbieżności populacji zróżnicowanej do określonych wartości, bo nowe przedziały przeszukiwania rozwiązania zależą także od populacji najlepszej.

\begin{equation}
\forall_{x^1 \in R_1 \cup R_2} d(x, x^1) = \sum_{i = 1}^{N} |x - x^1|
\end{equation}
\begin{equation}
D(x, R_1) = \sum_{x^1 \in R_1 \cup R_2} d(x, x^1)
\end{equation}

\subsection[Dodatkowe usprawnienia]{Dodatkowe usprawnienia}
Populacja zróżnicowana jest inicjowana na nowo, jeżeli w ciągu \texttt{T} kolejnych iteracji nie znaleziono nowego minimum (\texttt{T} jest jednym z parametrów algorytmu).\\

\subsection[Schemat ogólny zastosowanego algorytmu]{Schemat ogólny zastosowanego algorytmu}
Uproszczony schemat ogólny algorytmu w pseudokodzie (w szczególności, w kodzie źródłowym nazwy poszczególnych metod i ich parametry są inne):\\\\
\noindent //czyta dane z pliku\\
\noindent \texttt{READ\_DATA(file)} \\
\noindent //inicjuje obie populacje (zróżnicowaną i najlepszą)\\
\noindent \texttt{INIT\_BOTH\_POPULATIONS(DIV\_POP, BEST\_POP)}\\
\noindent //heurystyka usprawniająca \\
\noindent \texttt{BEST\_POP\_UPDATE(BEST\_POP)}\\
\noindent //warunkiem końcowym jest osiągnięcie zadanej liczby iteracji\\
\noindent \texttt{FOR (i = 0; i < MAX-ITER; i++)} \\
\noindent \texttt{\{}
\par //jeżeli w poprzednich T iteracjach nie dodano żadnego nowego rozwiązania
\par \texttt{if (!added)}
\par \texttt{\{}
\par \aindent //inicjujemy na nowo zróżnicowaną populację
\par \aindent \texttt{INIT\_DIV\_POPULATION(DIV\_POP)}
\par \texttt{\}}
\par // krzyżowanie osobników
\par \texttt{CHILDREN = CROSSOVER(DIV\_POP, BEST\_POP)}
\par // podmiana starego pokolenia na nowe
\par \texttt{(DIV\_POP, BEST\_POP) = REPLACEMENT(CHILDREN, DIV\_POP, BEST\_POP)}
\par //heurystyka usprawniająca
\par \texttt{BEST\_POP\_UPDATE(BEST\_POP)}\\
\noindent \texttt{\}}\\

\section[Obsługa programu]{Obsługa programu}

\subsection[Kompilacja i uruchamianie]{Kompilacja i uruchamianie}
Program został napisany w całości w języku \texttt{C++} przy użyciu zestawu narzędzi programistycznych
Dev-C++ w wersji 4.9.9.2.\\
Nie gwarantuję, że przy innej wersji zintegrowanego środowiska programistycznego,
a w szczególności innej wersji kompilatora języka \texttt{C++} program będzie działał
poprawnie. Aplikacja była testowana pod systemem Windows XP Professional z zainstalowanym
dodatkiem Service Pack 2 i jest przeznaczona wyłącznie dla systemów
operacyjnych Microsoft Windows.\\
Kod źródłowy implementacji znajduje się w całości w pliku \texttt{main.cpp}.

\subsection[Wywołanie i parametr algorytmu]{Wywołanie i parametr algorytmu}
Funkcją wywołującą algorytm jest: \texttt{sekwencyjny}.
Domyślnie funkcja jest wywoływana w procedurze \texttt{main} aplikacji.\\
Przed uruchomieniem algorytmu należy ustawić następujące parametry (stałe zdefiniowane na początku kodu źródłowego):
\begin{itemize}
    \item[-] wielkość populacji zróżnicowanej i najlepszej (stała \texttt{P}, domyślnie \texttt{P = 100}) -- łączna wielkość populacji wynosi, więc \texttt{2P};
    \item[-] liczba iteracji (stała \texttt{MAX\_ITER}, domyślnie \texttt{MAX\_ITER = 50});
    \item[-] rozmiar zadania (stała \texttt{N}), powinna być równa rozmiarowi testu, który zostanie zadany na wejście algorytmu (program rezerwuje sobie potrzebną pamięć);
    \item[-] częstotliwość generowania populacji zróżnicowanej przy niezmiennym w kolejnych iteracjach minimum (stała \texttt{T}), domyślnie \texttt{T = 5}.
\end{itemize}

\noindent Pozostałe parametry dostarczane są wraz z plikiem z danymi, jego struktura została omówiona w jednym z poprzednich działów tej pracy.\\
\noindent Przykładowe wywołanie skompilowanego programu:\\
\noindent \texttt{Projekt.exe < plik.dat}, gdzie \texttt{plik.dat} to plik z danymi o odpowiedniej strukturze.\\
Pliki z testami ze strony \cite{QAPL} zostały dołączone do tego projektu.
\section[Testy]{Testy}

\subsection[Test Wil100]{Test Wil100}
Wil100 jest testem rozmiaru \texttt{N = 100} dostępnym w \cite{QAPL}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  100\\
\hline
MAX\_ITER & 100 \\
\hline
P & 2*70\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent
\textbf{Wynik testu jest gorszy od najlepszego znanego rozwiązania o ok. 1.6\%.
Najlepsze znane rozwiązanie (wygenerowane przez hybrydowy algorytm genetyczny) nie jest optymalnym rozwiązaniem tego testu (jest gorsze od optymalnego ok. 3.4\%).} Według strony QAPLIB
istnieje pewna graniczna wartość, która jest możliwa do osiągnięcia ale nieznana jest permutacja, która tę wartość generuje.\\


\textbf{Wyniki pokazują wyraźnie szybką zbieżność w kierunku najlepszego rozwiązania, która po wykonaniu ok. 15 iteracji wyraźnie słabnie.}
W dalszej części działania algorytmu zbieżność jest wyraźnie słabsza, a ewolucja utknęła kilkakrotnie w ekstremum lokalnym (na wykresie są to niewielkie przedziały, gdzie funkcja jest stała). Udało się jednak w kilku przypadkach wyjść z pola przyciągania ekstremum lokalnego, prawdopodobnie dzięki heurystyce, która co \texttt{T} iteracji bez poprawienia minimum losuje na nowo populację zróżnicowaną. Usprawnienie to powoduje, że algorytm jest zmuszony przeszukiwać dotychczas niezbadane rejony przestrzeni, co owocuje nieznaczną ale jednak, poprawą wartości funkcji celu.

     \begin{figure}[!hbp]
       \caption{Wykres dla testu Wil100}
	    \label{fig:resultwil100}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resultwil100}
     \end{figure}
\newpage


\subsection[Test Sko100f]{Test Sko100f}
Sko100f jest testem rozmiaru \texttt{N = 100} dostępnym w \cite{QAPL}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  100\\
\hline
MAX\_ITER & 100 \\
\hline
P & 2*150\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent
\textbf{Wynik testu jest gorszy od najlepszego znanego rozwiązania o ok. 1.99\%.
Najlepsze znane rozwiązanie (wygenerowane przez hybrydowy algorytm genetyczny) nie jest optymalnym rozwiązaniem tego testu (jest gorsze od optymalnego aż ok. 6.43 \%, więc jest to test, który sprawia ogólnie dosyć poważne problemy algorytmom heurystycznym).} Według strony QAPLIB
istnieje pewna graniczna wartość, która jest możliwa do osiągnięcia ale nieznana jest permutacja, która tę wartość generuje.\\
\textbf{Pierwsze 14 iteracji wykonania algorytmu to bardzo szybka zbieżność w kierunku najlepszego rozwiązania.} W dalszej części wykonania programu zbieżność wyraźni słabnie i nieco zwiększa ok. 25 iteracji, kończąc się w 28. iteracji (od tej iteracji aż do końca funkcja jest stała).

     \begin{figure}[!hbp]
       \caption{Wykres dla testu Sko100f}
	    \label{fig:resultsko100f}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resultsko100f}
     \end{figure}
\newpage


\subsection[Test Esc128]{Test Esc128}
Esc128 jest testem rozmiaru \texttt{N = 128} dostępnym w \cite{QAPL}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  128\\
\hline
MAX\_ITER & 100 \\
\hline
P & 2*110\\
\hline
T & 10\\
\hline
\end{tabular}
\\
\noindent

\textbf{Wynik testu wyrównuje najlepszy znany wynik osiągnięty przez algorytm heurystyczny.
Najlepsze znane rozwiązanie (wygenerowane również przez algorytm greedy randomized adaptive search) nie jest optymalnym rozwiązaniem tego testu (jest gorsze od optymalnego aż  o ok. 96.86 \%).} Algorytmy heurystyczne nie radzą sobie z tym "złośliwym" testem, prawdopodobnie dlatego, że najlepsze rozwiązanie, które generuje wynik równy 2, jest bardzo odległe od innych ekstremów, których przyciąganie jest silniejsze, w tym od najlepszego wygenerowanego tego typu algorytmem osobnika, który generuje wynik równy 64. Wynik świadczy o ograniczeniu i niebezpieczeństwach związanych z ewolucją przy specjalnie "złośliwie" dobranych testach .\\

     \begin{figure}[!hbp]
       \caption{Wykres dla testu Esc128}
	    \label{fig:resultesc128}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=8cm, height=8cm]{resultesc128}
     \end{figure}

\subsection[Test Tho150]{Test Tho150}
Tho150 jest testem rozmiaru \texttt{N = 150} dostępnym w \cite{QAPL}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  150\\
\hline
MAX\_ITER & 100 \\
\hline
P & 2*110\\
\hline
T & 10\\
\hline
\end{tabular}
\\
\noindent

\textbf{Wynik testu jest gorszy od najlepszego znanego rozwiązania o ok. 1.8\%.
Najlepsze znane rozwiązanie (wygenerowane przez algorytm simulated jumping) nie jest optymalnym rozwiązaniem tego testu (jest gorsze od optymalnego ok. 6.3 \%).} Według strony QAPLIB
istnieje pewna graniczna wartość, która jest możliwa do osiągnięcia ale nieznana jest permutacja, która tę wartość generuje.\\

\textbf{Wyniki świadczą o bardzo szybkiej zbieżność w kierunku najlepszego rozwiązania, która po wykonaniu ok. 15 iteracji wyraźnie słabnie.}
W ciągu kolejnych iteracji wynik nie ulega poprawie, funkcja jest, więc stała na przedziale ok. [15, 30] iteracji.
\textbf{Później jednak następuje bardzo wyraźny skok. Wyjście z pola przyciągania ekstremum lokalnego, udało się prawdopodobnie dzięki heurystyce, która co \texttt{T} iteracji bez poprawienia minimum losuje na nowo populację zróźnicowaną, a algorytm ją poprawia w kolejnych iteracjach.}\\
Kolejny przestój przypadł na iteracje ok. [35, 45] ale został przełamany i wartość funkcji celu dla najlepszego osobnika w populacji wyraźnie spadła w iteracjach ok. [45, 58]. Dalsza ewolucja nie zmieniła już najlepszego rozwiązania.


     \begin{figure}[!hbp]
       \caption{Wykres dla testu Tho150}
	    \label{fig:resulttho150}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resulttho150}
     \end{figure}
\newpage

\subsection[Test Inst200]{Test Inst200}
Inst200 jest testem rozmiaru \texttt{N = 200}, największym dostępnym w \cite{GIN}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  200\\
\hline
MAX\_ITER & 50 \\
\hline
P & 2*100\\
\hline
T & 10\\
\hline
\end{tabular}
\\
\noindent

\textbf{Wynik testu jest gorszy od rozwiązania optymalnego o ok. 0.34\% (strona nie dostarcza informacji o tym jak z tym testem radzą sobie algorytmy heurystyczne).}

\textbf{Zbieżność w kierunku najlepszego rozwiązania jest bardzo wyraźna, ale dosyć krótka (trwa przez pierwsze 12 iteracji algorytmu i przy tym skuteczna).} W ciągu wyżej wspomnianych iteracji algorytmowi udaje się wygenerować bardzo dobre rozwiązanie, które następnie nie zmienia się znacząco w ciągu kolejnych iteracji z przedziału ok. [12, 23]. Ostatecznie ok. 23 iteracji udaje się jeszcze poprawić najlepsze rozwiązanie, które jest bardzo bliskie optymalnemu, ale dalsza ewolucja nie zmieniła już najlepszego rozwiązania.


     \begin{figure}[!hbp]
       \caption{Wykres dla testu Inst200}
	    \label{fig:resultinst200}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resultinst200}
     \end{figure}
\newpage

\subsection[Test Tai256c]{Test Tai256c}
Tai256c jest testem rozmiaru \texttt{N = 256}, największym dostępnym w \cite{QAPL}.
Parametry algorytmu:\\


\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  256\\
\hline
MAX\_ITER & 100 \\
\hline
P & 2*120\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent

\textbf{Wynik testu jest gorszy od najlepszego znanego rozwiązania o ok. 0.55\%.
Najlepsze znane rozwiązanie (wygenerowane przez algorytm mrówkowy) nie jest optymalnym rozwiązaniem tego testu (jest gorsze od optymalnego ok. 2.03 \%).} Według strony QAPLIB
istnieje pewna graniczna wartość, która jest możliwa do osiągnięcia ale nieznana jest permutacja, która tę wartość generuje.\\

\textbf{Bardzo szybka zbieżność w kierunku najlepszego rozwiązania, po wykonaniu ok. 18 iteracji wyraźnie słabnie.}
Najlepsi osobnicy w kolejnych iteracjach na przedziale ok. [18, 32] nie ulegają znacznej poprawie. Zbieżność przyspiesza natomiast w trakcie iteracji na przedziale ok. [32, 42] (algorytmowi udało się jeszcze wyjść z ekstremum lokalnego na kilka iteracji). Dalsza ewolucja, w kolejnych iteracjach nie przynosi już żadnej korzystnej dla algorytmu zmiany (funkcja jest, więc stała na przedziale ok. [42, 50] iteracji).

     \begin{figure}[!hbp]
       \caption{Wykres dla testu Tai256c}
	    \label{fig:resulttai256c}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resulttai256c}
     \end{figure}
\newpage

\subsection[Test Sko100c]{Test Sko100c}
Sko100c jest testem o rozmiarze \texttt{N = 100}. Test pochodzi ze strony \cite{QAPL}.
Parametry algorytmu:\\

\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  100\\
\hline
MAX\_ITER & 35 \\
\hline
P & 2*100\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent
\newline

Najlepsze znane rozwiązanie tego problemu wynosi 147862 i jest o około 5.73\% gorsze od rozwiązania optymalnego. \textbf{Nasz algorytm rozwiązał problem zwracając wynik 151651, czyli o 2,6\% gorszy}.\\

Początkowo, przez około 12 iteracji obserwujemy bardzo szybką zbieżność, która następnie słabnie, aby między iteracjami 15 a 20 całkowicie ustabilizować się na poziomie 152295. W okolicy 20 iteracji algorytmowi  udaje się jeszcze lekko zoptymalizować wynik uzyskując 151651.

    \begin{figure}[!hbp]
        \caption{Wykres dla testu Sko100c}
	    \label{fig:resultsko100c}
	       \centering
	           \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resultsko100c}
    \end{figure}
    \newpage

\subsection[Test Inst100]{Test Inst100}
Inst100 to test o rozmiarze \texttt{N = 100}. Test pochodzi ze strony \cite{GIN}.
Do testu użyto nastepujących parametrów algorytmu:\\

\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  100\\
\hline
MAX\_ITER & 25 \\
\hline
P & 2*100\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent
\newline    

Podobnie jak w poprzednich testach, badanie pokazało bardzo szybką początkową zbieżność. Algorytm poprawiał wynik do iteracji 12, potem ustabilizował się na ostatecznym poziomie. \textbf{Nasz algorytm uzyskał wynik 15087882, zaledwie o 0,05\% gorszy od najlepszego znanego rozwiązania}. Niestety strona, z której pochodzą dane nie zawiera informacji o tym, w jaki sposób został on uzyskany.\\

    \begin{figure}[!hbp]
       \caption{Wykres dla testu Inst100}
	    \label{fig:resultew100}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resultew100}
     \end{figure}
     \newpage 
     
\subsection[Test Tai150b]{Test Tai150b}
Test Tai150b pochodzi ze strony \cite{QAPL} i ma rozmiar \texttt{N = 150}. 
Do testu użyto nastepujących parametrów algorytmu:\\

\begin{tabular}{||c|c||} \hline
\multicolumn{2}{||c||}{Parametry dla algorytmu} \\ \hline
N &  100\\
\hline
MAX\_ITER & 40 \\
\hline
P & 2*100\\
\hline
T & 5\\
\hline
\end{tabular}
\\
\noindent
\newline

Ostatni wykonany przez nas test ma najlepsze rozwiązanie na poziomie 498896643, czyli o 12.66\% gorsze od optymalnego. \textbf{Nasz algorytm  znalazł rozwiązanie 508537483. Jest ono jedynie nieznacznie gorsze od najlepszego (o 1,9\%).}\\

Analiza najlepszego rozwiązania w poszczególnych iteracjach pokazuje silną początkową zbieżność trwającą do około 15 iteracji. Kolejne iteracje nie poprawiają już wyniku.\\ 
    
    \begin{figure}[!hbp]
       \caption{Wykres dla testu Tai150b}
	    \label{fig:resulttai150b}
	      \centering
	        \includegraphics[type=eps,ext=.eps,read=.eps,width=14cm, height=14cm]{resulttai150b}
     \end{figure}
        \newpage              

\subsection[Wnioski z testowania]{Wnioski z testowania}
Badanie pokazało, że zastosowanie algorytmów ewolucyjnych wspomaganych różnymi heurystykami do rozwiązywania NP-trudnych, kombinatorycznych problemów takich jak QAP znajduje swoje uzasadnienie w praktyce. Algorytm we wszystkich opisanych testach znalazł rozwiązania niewiele gorsze od najlepszych znanych (w jednym przypadku udało się wyrównać najlepszy znany wynik). Ponadto na podstawie wyników ze strony QAP można zauważyć, że nie istnieje obecnie ani jeden algorytm heurysytyczny, który radziłby sobie wzorowo ze wszystkimi testami (najlepsze znane rezultaty są osiągane przez wiele implementacji, różnych algorytmów, nie tylko ewolucyjnych).\\
Z eksperymentów można wywnioskować, że trudność testów dla poszczególnych instancji problemu QAP zależy nie tylko od ich wielkości, ale także od ilości ekstremów lokalnych oraz umiejętnego generownia tego typu testów (istnieje w Internecie kilka projektów naukowych, które zajmują się generowaniem samych instancji dla problemu QAP). Ponadto na podstawie strony \cite{QAPL} można zauważyć, że istnieje wiele testów znaczenie mniejszych, niż te opisane w naszej pracy, które mimo niewielkiego rozmiaru nie zostały zotpymalizowane żadnym algorytmem heurystycznym (problemy pojawiają się nawet przy testach wielkości 30).

\begin{thebibliography}{9}
\bibitem{QAPL} {\it http://www.seas.upenn.edu/qaplib/inst.html (ostatni dostęp 29.01.2011)}.
\bibitem{GIN} {\it http://www.soften.ktu.lt/~gintaras/qproblem.html (ostatni dostęp 29.01.2011)}.
\end{thebibliography}

     
\end{document}


